package sort;

/**
 * Created by Ghost on 2014/12/24 0024.
 */
public class MergeSort {
    private int[] merge(int[] a, int[] b){
        int[] rst = new int[a.length+b.length];
        int aPoint = a.length-1, bPoint = b.length-1;
        int i = rst.length-1;
        while(i>=0){
            if(aPoint>=0 && bPoint>=0){
                if(a[aPoint]>b[bPoint]){
                    rst[i]=a[aPoint];
                    aPoint--;
                    i--;
                } else{
                    rst[i] = b[bPoint];
                    bPoint--;
                    i--;
                }
            }
            else if(aPoint>=0 && bPoint<0){
                for(;aPoint>=0;aPoint--,i--){
                    rst[i] = a[aPoint];
                }
            } else{
                for(;bPoint>=0;bPoint--,i--){
                    rst[i] = b[bPoint];
                }
            }
        }
        return rst;
    }
    public int[] sort(int[] num){
        if(num.length>1){
            int mid = num.length>>1;
            int[] a = new int[mid];
            int[] b = new int[num.length-mid];
            for(int i=0;i<mid;i++){
                a[i] = num[i];
            }
            for(int i=mid;i<num.length;i++){
                b[i-mid] = num[i];
            }

            int[] rsta = sort(a);
            int[] rstb = sort(b);
            return merge(rsta,rstb);
        }
        else
            return num;
    }

    public static void main(String[] args){
        MergeSort mergeSort = new MergeSort();
        int[] num = {7,6,5,4,3,2,1};
        int[] rst = mergeSort.sort(num);
        for(int i=0;i<rst.length;i++){
            System.out.print(" "+rst[i]);
        }
    }
}
